/**
 * @file minimum_path.cpp
 * @author 米新举 (mixinju@outlook.com)
 * @brief 最短路径问题
 * @version 0.1
 * @date 2022-01-05
 *
 * @copyright Copyright (c) 2022
 *
 */

#include <bits/stdc++.h>

/**
 * @brief Dijkstra 算法求最短路径
 *
 * @param matrix 邻接矩阵存图
 * @param origin 最短路径其实顶点
 * @return std::pair<int32_t, std::vector<int32_t>>
 */
std::pair<int32_t, std::vector<int32_t>> Dijkstra(
    std::vector<std::vector<int32_t>>& matrix, int origin = 0) {
  int32_t num_vertex = matrix.size();
  std::vector<int32_t> path;  //记录路径
  path.emplace_back(origin);

  std::bitset<100> visited(0);  //记录是否被访问过
  int64_t sum_of_path{0};       // 路径的和

  std::vector<int32_t> distance(num_vertex, 0);
  //初始化
  for (int v_id = 0; v_id < num_vertex; v_id++) {
    distance.at(v_id) = matrix.at(origin).at(v_id);
  }

  while (path.size() <= num_vertex) {
    int32_t next_vertex = (origin + 1) % num_vertex;  // 记录下一个顶点

    // 寻找距离已经形成的距离起点最近的点
    int32_t minimum_distance = INT16_MAX;
    for (int32_t v_id = next_vertex; v_id < num_vertex; v_id++) {
      if (!visited[v_id] && distance.at(v_id) < minimum_distance) {
        minimum_distance = distance.at(v_id);
        next_vertex = v_id;
        path.emplace_back(next_vertex);  // 添加到路径上
      }
    }
    sum_of_path += minimum_distance;
    visited[next_vertex] = 1;  //标记为已经访问过

    for (int32_t v_id = 0; v_id < num_vertex; v_id++) {
      if (!visited[v_id] && matrix.at(next_vertex).at(v_id) <
                                distance.at(v_id) + minimum_distance) {
        distance.at(v_id) = matrix.at(next_vertex).at(v_id) + minimum_distance;
      }
    }
  }

  return {sum_of_path, path};
}

std::vector<std::vector<int32_t>> Floyd(
    std::vector<std::vector<int32_t>>& matrix) {
  // Floyd用来求彼此两个顶点之间的最短路径
  std::vector<std::vector<int32_t>> distance(matrix);  // 初始化和邻接矩阵一样
  int32_t num_vertex = matrix.size();
  for (int k = 0; k < num_vertex; k++) {
    for (int i = 0; i < num_vertex; i++) {
      for (int j = 0; j < num_vertex; j++) {
        distance.at(i).at(j) = std::min(
            distance.at(i).at(j), distance.at(i).at(k) + distance.at(k).at(j));
      }
    }
  }

  return distance;
}